Spatially periodic structures, that is to say image features that repeat over at least part of the image area can cause problems for some image processing tasks. (In the remainder of this specification periodicity means spatial periodicity unless another meaning is specifically stated.) Railings, empty seats in an Olympic stadium, and windows of skyscrapers are typical periodic structures. An example of an image processing task for which periodic structures are problematic is motion compensated frame rate interpolation, and the difficulties of a particular case will now be explained with reference to FIGS. 1 to 3.
FIG. 1 shows one-dimensional sections through two successive frames (101), (102) in a time sequence of sampled images, referred to as the previous frame (101) and next frame (102). A set of adjacent pixels along a particular direction within a particular image region is represented by small circles in the Figure. The luminance values of the pixels are represented by the fill pattern of the circles, and, for simplicity it is assumed that only three luminance values exist—represented by white fill, hatched fill, and black fill.
The spatial sequence of pixel values comprises a periodic structure with a period of six pixel pitches (103). This structure moves, over a distance of two pixel pitches, to a new position in the next frame (102). This is indicated by the motion vector (105) which is shown pointing from a pixel (106) in the previous frame to a matching pixel (107) in the next frame. An incorrect motion vector (108) is also shown, with a motion of four times the pixel pitch in the opposite direction. Though incorrect with regard to the actual motion of the structure, this second motion vector (108) represents an equally valid interpretation of the local information in the two images, demonstrated by the exact matching of the values of pixels (106) and (109).
For some applications of motion estimation, incorrect motion vectors arising from periodic structures do not pose a significant problem. For example, in compression involving motion compensated interframe prediction, the prediction resulting from such an incorrect vector may be as good as that resulting from the correct vector. The only disadvantage in using the incorrect vector is that the motion vectors may be less consistent, so the cost of transmitting motion vectors may increase slightly.
For other applications, such as motion compensated frame rate interpolation, incorrect motion vectors arising from periodic structures may significantly degrade the performance of the interpolation. In FIG. 2, interpolation of an intermediate image (203) using correct motion vectors is shown. In this exemplary motion-compensated process, the interpolated output frame (203) is derived from the combination of: a frame (205) that is a shifted version of the previous frame (201); and, a frame (207) that is a shifted version of the next frame (202). For clarity the two contributing frames are shown in the Figure adjacent to the position of the output frame (203), however their true positions coincide with position of the output frame (203).
Pixels are projected from the previous image (201) according to a correct forward vector (204) to form the forward projected image (205), and pixels are projected from the next image (202) according to a correct backward vector (206) (which is equal in size and opposite in direction to the forward vector) to form the backward projected image (207). The average of the two (in this case identical) projected images is used to produce the interpolated output image (203).
We now consider an example, illustrated in FIG. 3, where one of the motion vectors, in this case the backward vector (306), is incorrect because of the ambiguity arising from the periodic structure. The backward projected frame (307) now has a spatial phase difference of 180° (three pixel pitches) with respect to the forwards projection, with the result that the two contributions (305), (307) to the interpolated result (303) are misaligned and make an incorrect interpolated image (303). The resulting interpolated moving sequence would have significant flicker and motion judder.
Several methods for detecting and for correcting for periodic structures in images have been proposed. In U.S. Patent 2010/008423, Namboodiri et al disclose a method for periodic structure detection in which significant peaks are sought in the two-dimensional frequency-domain representation of blocks in a picture. In “Detecting Periodic Structures”, Orwell et al [Orwell, J. M. and Boyce, J. F. ‘Detecting Periodic Structures’, Proc. Fourteenth International Conference on Pattern Recognition, 1998, pp. 714-716] disclose a method for periodic structure detection based on feature detection followed by an autocorrelation process on the detected features. In “Periodicity, directionality and randomness: Wold features for image modeling and retrieval” Liu and Picard [Liu, F. and Picard, R. W. ‘Periodicity, directionality and randomness: Wold features for image modeling and retrieval’, IEEE Trans. on PAMI, vol. 18, no. 7, July 1996, pp. 722-733] disclose a method for periodic structure detection based on image autocovariance functions. In U.S. Pat. No. 5,793,430, Knee et al disclose a method based on analysing a line of block-based displaced frame differences in a block matching motion estimator.
The prior-art methods are either very complex to implement, fail to detect periodic structures with multiple dominant frequency components, or give “false alarms” on non-periodic structures such as straight edges. The present invention addresses some or all of these deficiencies of the prior art.